package sort;

import java.util.Arrays;

public class QuickSort_T {
    public static void main(String[] args) {
        int[] a = {1,6,1,2,3,3,6,6,8,9}; //{2,6,1,5,8,3,2,6,8,1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
    /*
        1. 用left和right标出处理范围，最初从0到length-1范围进行处理
        2. 选取第一个值作为基准值
        3. 下标i和j，分别从left和right开始
        4. j循环向左移动，如果找到>=基准值的值，继续向左，否则停下
        5. j位置找到的小值，踢到i位置
        6. i循环向右移动，如果找到<=基准值的值，继续向右，否则停下
        7. i位置找到的大值，踢到j位置
        8. i和j重合时，循环停止
        9. 基准值放入i位置
        10. 递归处理左侧的 left到i-1 范围
        11. 递归处理右侧的 i+1到right 范围

        最简问题：一个值（left和right重合），没有值（left>right）
     */
    private static void sort(int[] a) {
        sort(a, 0, a.length-1);
    }
    private static void sort(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int base = a[left];
        int i = left;
        int j = right;
        while (i<j) { //i,j不重合就继续执行
            while (i<j && a[j]>=base) {
                j--;
            }
            a[i] = a[j];

            while(i<j && a[i]<=base) {
                i++;
            }
            a[j] = a[i];
        }
        a[i] = base;
        sort(a, left, i-1);
        sort(a, i+1, right);
    }
}
